#include<iostream>
#include<algorithm>
#include "queue"


/**
 * # 以下内容结合自己总结的915知识点进行记忆！
 *
 * */
using namespace std;

//[ ]
int binarySearch(int *nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else left = mid + 1;
    }
    return -1;
}

//[ )
int binarySearch_2(int *nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid;
        } else left = mid + 1;
    }
    return -1;
}

//(]
int binarySearch_3(int *nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else left = mid;
    }
    return -1;
}

//( )
int binarySearch_4(int *nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid;
        } else left = mid;
    }
    return -1;
}

int find_left_1(int nums[], int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            if (mid == 0 || nums[mid - 1] < target) return mid;
            else right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else left = mid + 1;
    }
    return -1;
}

int find_right_1(int nums[], int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            if (mid == numsSize - 1 || nums[mid + 1] > target) return mid;
            else left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else left = mid + 1;
    }
    return -1;
}

int find_left_2(int nums[], int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else left = mid + 1;
    }
    if (left >= numsSize || target != nums[left]) return -1;
    return left;
}


int find_right_2(int nums[], int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (nums[mid] == target) {
            left = mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else left = mid + 1;
    }
    if (right < 0 || target != nums[right]) return -1;
    return right;
}

int main() {
    int num[10] = {0, 1, 2, 3, 4, 4, 4, 5, 5, 5};
    int num1[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    for (int i = 0; i < 10; ++i) {
        int left = find_left_1(num, 10, i);
        int r = find_right_1(num, 10, i);
        cout << left << " " << r << endl;
    }
    cout << "==================" << endl;
    for (int i = 0; i < 10; ++i) {
        int left = find_left_2(num, 10, i);
        int r = find_right_2(num, 10, i);
        cout << left << " " << r << endl;
    }

    return 0;

}
